package com.leetcode.BinaryTree;

import java.time.chrono.IsoChronology;

//验证二叉搜索树
public class lc_98 {
    public static void main(String[] args) {

    }

    //给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
    public boolean isValidBST(TreeNode root) {
        //1.判断,不需要构建全局变量,但传入参数需要最大最小范围,所以需要构建方法
        // 处理特殊情况：空树或单节点树
        if (root == null) {
            return true;  // 空树被视为有效BST
        }
        if (root.left == null && root.right == null) {
            return true;  // 单节点树被视为有效BST
        }
        return isValid(root, Long.MAX_VALUE, Long.MIN_VALUE);
    }

    public boolean isValid(TreeNode root, long max, long min){
        //2.传入参数:本层树的根结点,左右范围 返回参数:boolean型,是否为二叉搜索树
        //3.终止条件:如果为null,直接返回true
        if (root == null) {
            return true;
        }
        //4.每一层逻辑:
        //对于根结点,值大于max或小于min直接返回false
        if (root.val >= max || root.val <= min) {
            return false;
        }
        //对底层进行判断,只有左右子树满足的时候才返回true
        //左子树的最小值为min,最大值为root,val  右子树的最大值为max,最小值为root.val
        return isValid(root.left, root.val, min) && isValid(root.right, max, root.val);
    }

    //方法二:只用中序遍历,二叉搜索树中序遍历严格单调递增的性质

    long pre = Long.MIN_VALUE;
    public boolean isValidBST2(TreeNode root) {
        //1.边界条件
        if (root == null) {
            return true;
        }
        //2.每一层逻辑:
        //访问左子树
        if(!isValidBST2(root.left)){
            return false;
        }
        //访问当前结点:如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
        if(root.val <= pre){
            return false;
        }
        pre = root.val;
        //访问右子树
        return isValidBST2(root.right);
    }
}
